# 给你一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。
#
# 请返回这个数组中 「优美子数组」 的数目。
#  示例 1：
# 输入：nums = [1,1,2,1,1], k = 3
# 输出：2
# 解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
#
#  示例 2：
# 输入：nums = [2,4,6], k = 1
# 输出：0
# 解释：数列中不包含任何奇数，所以不存在优美子数组
#
# 示例 3：
# 输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
# 输出：16
from typing import List


class Solution:
    """
    要满足 nums[i] ~ nums[j] 中有 k 个奇数，那么意思是只关心 nums[i]是否为奇数，可以对 nums[i] % 2 ,就可以将该数组全部转成0, 1
    就可以转化成统计 new_nums[i] ~ new_nums[j] 的和为 k 的子序列的个数
    进一步转化成找到一个连续子数组，使得子数组的和等于 k 的个数（leetcode560），就可以用前缀和了
    """

    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        res = 0
        # 先得到新 new_nums 数组
        new_nums = [n % 2 for n in nums]
        # 转化成找到一个连续子数组，使得子数组的和等于 k 的个数（leetcode560）
        counts_map = {0: 1}  # key 为 前缀和， value 为 前缀和为 key 的个数
        tmp_pre_sum = 0
        for n in new_nums:
            tmp_pre_sum += n
            res += counts_map.get(tmp_pre_sum - k, 0)
            counts_map[tmp_pre_sum] = counts_map.get(tmp_pre_sum, 0) + 1
        return res


if __name__ == '__main__':
    nums, k = [1, 1, 2, 1, 1], 3
    nums, k = [2, 2, 2, 1, 2, 2, 1, 2, 2, 2], 2
    print(Solution().numberOfSubarrays(nums, k))
